#ifndef TRIE_TEMPLATE_H
#define TRIE_TEMPLATE_H

#include "GlobalMacros.h"

#include <unordered_map>
#include <vector>

NAMESPACE_BEGIN
template<class T>
class TrieTemplate
{
protected:
	std::unordered_map<T, TrieTemplate<T>*> children;
	bool if_end;
public:
	TrieTemplate();
	~TrieTemplate();
public:
	TrieTemplate<T>* search(const std::vector<T>& prefix);
	void insert(const std::vector<T>& word);
	void getSuffix(std::vector<std::vector<T>>& all_suffix);
};
NAMESPACE_END

template<class T>
inline nmspc::TrieTemplate<T>::TrieTemplate() :children(std::unordered_map<T, nmspc::TrieTemplate<T>*>()), if_end(true)
{
}

template<class T>
inline nmspc::TrieTemplate<T>::~TrieTemplate()
{
	this->if_end = false;
	for (auto iter = this->children.begin(); iter != this->children.end(); iter++)
	{
		if (iter->second != nullptr)
		{
			delete iter->second;
			iter->second = nullptr;
		}
	}
	this->children.clear();
}

template<class T>
inline nmspc::TrieTemplate<T>* nmspc::TrieTemplate<T>::search(const std::vector<T>& prefix)
{
	nmspc::TrieTemplate<T>* node = this;
	for (const char& ch : prefix)
	{
		if (!node->children.count(ch))
		{
			return nullptr;
		}
		node = node->children[ch];
	}
	return node;
}

template<class T>
inline void nmspc::TrieTemplate<T>::insert(const std::vector<T>& word)
{
	nmspc::TrieTemplate<T>* node = this;
	for (const T& ch : word)
	{
		if (node->if_end == true)
		{
			node->if_end = false;
		}
		if (!node->children.count(ch))
		{
			node->children[ch] = new nmspc::TrieTemplate<T>();
		}
		node = node->children[ch];
	}
	node->if_end = true;
}

template<class T>
inline void nmspc::TrieTemplate<T>::getSuffix(std::vector<std::vector<T>>& all_suffix)
{
	static std::vector<T> cur_suffix = {};
	if (this->if_end == true)
	{
		if (cur_suffix.size() == 0) all_suffix.push_back(cur_suffix);
	}
	for (std::unordered_map<T, nmspc::TrieTemplate<T>*>::iterator iter = this->children.begin(); iter != this->children.end(); iter++)
	{
		cur_suffix.push_back(iter->first);
		iter->second->getSuffix(all_suffix);
	}
	if (cur_suffix.size() == 0)return;
	cur_suffix.pop_back();
}

#endif // !TRIE_TEMPLATE_H
